package com.zklh.leetcode.dynamic;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 最大正方形
 *
 * @author tongnan
 * @date 2025/10/9
 */
public class Solution221 {
    /**
     * 这里利用队列扩展的
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        int XSize = matrix.length;
        int YSize = matrix[0].length;
        int[][] tierMaximalSquare = new int[XSize][YSize];
        Queue<int[]> tierMaximalLocQueue = new LinkedList<>();

        for (int x = 0; x < XSize; x++) {
            for (int y = 0; y < YSize; y++) {
                if (matrix[x][y] == '1') {
                    tierMaximalSquare[x][y] = 1;
                    tierMaximalLocQueue.add(new int[]{x, y});
                }
            }
        }

        int tier = 0;
        while (!tierMaximalLocQueue.isEmpty()) {
            tier++;
            int batchSize = tierMaximalLocQueue.size();
            for (int i = 0; i < batchSize; i++) {
                int[] peek = tierMaximalLocQueue.poll();
                if (peek[0]+tier >= XSize || tierMaximalSquare[peek[0]+1][peek[1]] == 0) {
                    tierMaximalSquare[peek[0]][peek[1]] = 0;
                    continue;
                }
                if (peek[1] + tier >= YSize || tierMaximalSquare[peek[0]][peek[1]+1] == 0) {
                    tierMaximalSquare[peek[0]][peek[1]] = 0;
                    continue;
                }
                if (matrix[peek[0]+tier][peek[1]+tier] == '0') {
                    tierMaximalSquare[peek[0]][peek[1]] = 0;
                    continue;
                }
                tierMaximalLocQueue.add(peek);
            }
        }

        return tier * tier;
    }

    public static void main(String[] args) {
        char[][] maxtrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
//        char[][] maxtrix = {{'0','1'}, {'1','0'}};
        Solution221 solution221 = new Solution221();

        int i = solution221.maximalSquare(maxtrix);
        System.out.println(i);
    }
}
